import java.util.HashMap;
import java.util.Map;

class SSolution{
    /**
     * 问题：查找旋转后升序数组的最小值
     * 链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
     * 时间复杂度：O(logN);
     * 空间复杂度：O(1);
     */

    public int findMin(int[] nums) {
        //1.处理已经是升序的情况
        int left = 0,right = nums.length - 1;

        if(nums[right] >= nums[left]) return nums[left];

        //2.分为两端区间，符合二段性
        while(left < right){
            int mid = left + (right - left) / 2;
            //3.边界问题： == 的时候右区间存在值
            //最小值位于右边
            if(nums[mid] >= nums[0]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }

    /**
     * 问题：求缺失的数
     * 链接：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
     * 时间复杂度：O();
     * 空间复杂度：O();
     */
    public int takeAttendance(int[] records) {
        int left = 0,right = records.length - 1;

        while(left < right){
            int mid = left + (right - left) / 2;

            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }

        return records[left] == left ? left + 1 : records[left] - 1;
    }

    //1.暴力解法
    public int takeAttendance1(int[] records) {
        //1.暴力解法
        int length = records.length;
        if(length == 1){
            if(records[0]== 0) return records[0] + 1;
            else return records[0] - 1;
        }
        int i = 1;
        for(;i < records.length;i++){
            if(records[i] != records[i - 1] + 1){
                return records[i] - 1;
            }
        }

        if(records[0] == 0) return length;
        else return 0;
    }

    //2.hash表
    public int takeAttendance2(int[] records) {
        //使用hash桶
        Map<Integer,Integer> hash = new HashMap<>();

        int i = 0,length = records.length;
        for(;i < length;i++){
            hash.put(records[i],1);
        }
        //转为数组
        i = 0;
        for(;i < length;i++){
            if(hash.getOrDefault(i,0) == 0)
                return records[i] - 1;;
        }

        //能走到中说明是有序且没有丢失数据
        if(records[0] == 0) return length;
        else return 0;
    }

    //3.高斯求和
    public int takeAttendance3(int[] records) {
        //高斯求和
        int length = records.length;
        long sum1 = (length * (length +1)) / 2;

        long sum2 = 0;
        for(int i = 0;i < length;i++){
            sum2 += records[i];
        }

        return (int)(sum1 - sum2);
    }

    public int takeAttendance4(int[] records) {
        //位运算
        int len = records.length;

        int ret = 0,i = 0;
        for(;i < len;i++){
            ret ^= records[i];
            ret ^= i;
        }

        return ret ^= i;
    }
}